“Bus arbitration” refers to controlling access to a shared data bus in order to utilize the bus efficiently and to ensure that each competing bus user has a fair opportunity to access the bus.
Many patents address the problem of bus arbitration. For example, U.S. Pat. No. 6,092,137 to Huang, et al. assigns each competing source (i.e., bus user) an adjustable priority weighting value (PWV) that is initially set to a value that reflects the bandwidth requirements of the competing source (CS). During arbitration, the competing source with the lowest PWV is granted access to the bus. For each arbitration in which CSi is not granted bus access, PWVi is reduced by one so that the longer CSi is denied bus access, the greater the likelihood that CSi will be chosen. After CSi is granted access, PWVi is reset to its initial value.
U.S. Pat. No. 6,092,137 further provides an arbitration protocol, which requires reduced circuit size to compare the priority values of the competing sources that have requested access to the shared data bus. This reduced circuit size is achieved by using a multi-level arbitration scheme. Initially, competing sources are classified into competing source groups based on their bandwidth requirements so that competing sources having the same, or similar, bandwidth requirements are assigned to the same group. Each competing source group is assigned to a first level arbiter, which may utilize conventional arbitration schemes such as round robin arbitration or first-come first-serve.
U.S. Pat. No. 5,528,767 to Chen describes a programmable multi-level bus arbitration apparatus for computer systems, which implements dynamic arbitration for the grant of control over a system bus by one of a number of bus master devices. A number of programmable restricters each receive a system bus request signal issued by a corresponding one of the bus master devices competing for the control over the system bus. The restricters block or relay the bus request signal. A programmable priority arbiter receives an output of each of the restricters for arbitration to grant control of the system bus to a selected one of the bus master devices based on a pre-programmed priority scheme. A communication protocol handler receives and monitors the status of the bus enable signal for generating a bus busy signal to control the issuing of a verified bus request signal by one of the restricters or the blocking of the bus request signal based on the status of the bus busy signal.
U.S. Pat. No. 6,157,989 to Collins describes an arbitration and task switching technique in a real-time multiprocessor data processing system having a common bus and a segmented shared memory, where fullness of memory segments of the shared memory is used as a measurement for arbitration and task switching priorities. A bus request mechanism in each of the processors dynamically calculates normalized priority values based on relative needs across the system. The normalized priority calculation is based on monitoring the fullness of memory segments of the shared memory associated with each processor of the system. Using this normalized priority calculation, the bus access order and bus bandwidth are optimally allocated according to tasks executed by the processors. Also, the normalized priority calculation and a preprogrammed threshold is used to control task switching in the multi-processor system.
U.S. Pat. No. 6,026,461 to Baxter describes a method of arbitrating requests for a system bus in a computer system by establishing a window for simultaneously capturing all requests for the system bus. The requests include information about a requested packet type, and an input queue state of the system bus requester. All requests for the system bus are captured during the window. The captured requests are prioritized into high, medium, and low priority based on the information included in the captured requests. Potential system bus targets are examined by their busy signals. Then low priority, medium priority, and high priority requesters are selected as potential bus grant candidates, and then actually granted the bus in accordance with the requests which have been time ordered.
U.S. Pat. No. 5,933,616 to Pecone, et al. describes a computer system wherein a bus master generates a signal indicative of the type of cycle it plans to initiate when requesting bus ownership. Other bus masters may be configured to generate similar cycle-type signals. A bus arbiter samples each master's unique cycle type signal during the request phase, and further receives information regarding the status of various target resources. Based upon the cycle type signals from requesting masters and upon the target resource information, the bus arbiter determines whether a master is planning to access an unavailable target resource. A master that is planning to access an unavailable target resource will be denied access of the bus. Accordingly, other masters intending to initiate cycles to available target resources may be granted ownership of the bus. As a result, target termination retry cycles may be avoided, and bus bandwidth and overall system performance may be improved.
U.S. Pat. No. 5,689,657 to Desor et al. describes a bus arbitration method for a multimaster system, comprising a plurality of masters sharing a global data bus and a plurality of bus arbiters sharing a global identification bus. Each active bus arbiter applies to the identification bus a bus request signal containing a k-bit-wide identification word representative of the priority of the master associated with the bus arbiter. In each prioritization step of the bus grant cycle, a logic level is produced on the identification bus by logically combining bits of equal significance. This logic level is then compared with the corresponding bits of the applied identification words. The k bits of the identification words of the bus arbiters are placed on the identification bus on a time-graded basis; in each prioritization step of the bus grant cycle, only those bits of the identification words are placed on the identification bus which are of equal significance, and in each prioritization step of the bus grant cycle, those bus arbiters whose identification word bit in the prioritization step does not match the logic level of the identification bus are eliminated from the bus arbitration of the bus gram cycle.